COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnify{1200}
C00009 ENDMK
C⊗;
\magnify{1200}
\def\xskip{\hskip7pt plus3pt minus4pt}
\chcode`|=13
\def|#1|{\hbox{\it#1\/}}
\def\IF{\mathop{\bf if}}
\def\THEN{\mathrel{\bf then}}
\def\ELSE{\mathrel{\bf else}}
\def\AND{\mathrel{\bf and}}
\def\OR{\mathrel{\bf or}}
\def\NOT{\mathop{\bf not}}
\def\N{\mathop{\bf n}}
\def\T{\hbox{\tt T}}
\def\NIL{\hbox{\tt NIL}}
\def\.{\mathbin{.}}
\def\A{\mathop{\bf a}}
\def\D{\mathop{\bf d}}
\def\EQ{\mathrel{\bf eq}}
\def\AT{\mathop{\bf at}}
\def\quote#1{\hbox{\sfcode`.=1000\tt#1}}
\def\list#1{\langle#1\rangle}

\ctrline{\bf CS 206---Recursive Programming and Proving}
\vskip 20pt
\ctrline{Midterm Examination}
\ctrline{November 4, 1982}
\vskip 20pt
\parindent 0pt
\parskip 4pt
\def\prob#1.{\bigbreak #1.\quad\ignorespace}

This examination is open book and notes.  Write LISP functions or
predicates except where something else is required.  Either external
or internal notation may be used.

\prob 1. [10 points]\quad
$|isordered|\,u$ determines whether a list of numbers is ordered, i.e.,
$$\lpile{|isordered|\,\quote{(1 4 5 7)}=\T,\cr
|isordered|\,\quote{(2 4 3)}=\NIL,\cr
|isordered|\,\quote{(7)}=\T.\cr}$$

\prob 2. [30 points]\quad $|remove|[x,u]$ returns the list $u$
with all top-level occurrences of $x$ removed.  This is similar to
the MacLisp function {\tt DELETE}, but {\tt DELETE} destructively
modifies $u$, which your function shouldn't do.  For example,
$$\lpile{|remove|[\quote{A},\quote{(A (B C) A D)}]=\quote{((B C) D)},\cr
|remove|[\quote{(B C)},\quote{(A (B C) A D)}]=\quote{(A A D)},\cr
|remove|[\quote{E},\quote{(A (B C) A D)}]=\quote{(A (B C) A D)}.\cr}$$
\item{a.} [10 points]\quad Write the function |remove|.
\par\noindent Now use induction to prove that
$$∀x\,u.\,|member|[x,|remove|[x,u]]=\NIL.$$
\item{b.} [10 points]\quad Identify the induction principle used and write
the formula $\Phi$ used in the induction.
\item{c.} [10 points]\quad Prove the basis and the inductive step, thus
completing the proof by induction.

\prob 3. [10 points]\quad Consider the following functions over the integers:
$$\eqalign{f[n]&←\IF n=0\THEN 0\ELSE f[n-2],\cr
g[n]&←\IF n=1\THEN 0\ELSE g[n-2],\cr
h[n]&←\IF n=0\THEN 0\ELSE h[n-1].\cr}$$
\item{a.} [4 points]\quad It is clear that
{\postdisplaypenalty 10000
$$∀n.\,f[n]=\IF n≥0\AND|even|[n]\THEN 0\ELSE\bot.$$}%
Provide similar statements about $g$ and $h$.\xskip (You do not need to
prove these statements.)
\item{b.} [6 points]\quad Which of the following statements are true?
\itemitem{i.} $f\sqsub g$,
\itemitem{ii.} $g\sqsub f$,
\itemitem{iii.} $f\sqsub h$,
\itemitem{iv.} $h\sqsub f$,
\itemitem{v.} $g\sqsub h$,
\itemitem{vi.} $h\sqsub g$.

\prob 4. [30 points]\quad $|simplify|\,|spexp|$ simplifies expressions made
up of sums and products, recognizing the following opportunities:
\item{$\bullet$} a 0 term in a sum is removed,
\item{$\bullet$} a sum with no terms becomes 0,
\item{$\bullet$} a sum with only one term becomes that term,
\item{$\bullet$} a 0 term in a product makes the whole product 0,
\item{$\bullet$} a 1 term in a product is removed,
\item{$\bullet$} a product with no terms becomes 1,
\item{$\bullet$} a product with only one term becomes that term,
\par\noindent Examples:
$$\lpile{|simplify|\,\quote{(PLUS X (TIMES 0 Y) 0)}=\quote{X},\cr
|simplify|\,\quote{(TIMES (PLUS A) (TIMES B 1 C) (TIMES))}=
\quote{(TIMES A (TIMES B C))},\cr
|simplify|\,\quote{(PLUS (TIMES (PLUS 1)) -1)}=\quote{(PLUS 1 -1)}.\cr}$$
The argument |spexp| may be a constant \quote{0} or \quote{1}, an atom,
which is interpreted as a variable, or a list of the form
$$\lpile{\quote{(PLUS |spexp| ... |spexp|) }\rm or\cr
\quote{(TIMES |spexp| ... |spexp|)}.\cr}$$
Efficiency of your program need not be considered.

\vfill\end

% Problems not used:

\prob 1. $|outerprod|[f,u,v]$, where $f$ is a function of two arguments,
$u=({u↓1}{u↓2}\ldots{u↓m})$, and $v=({v↓1}{v↓2}\ldots{v↓n})$,
returns
$$\vbox{\halign{\rt{#}&\lft{$#$}\quad&\lft{$#$}\quad&\lft{$#$}\quad&\lft{$#$}\cr
(&(f[u↓1,v↓1])&f[u↓1,v↓2]&\cdots&f[u↓1,v↓n])\cr
&(f[u↓2,v↓1])&f[u↓2,v↓2]&\cdots&f[u↓2,v↓n])\cr
&&\quad\cdots\cr
&(f[u↓m,v↓1])&f[u↓m,v↓2]&\cdots&f[u↓m,v↓n])).\cr}}$$

\prob 3. $|most|\,x$ returns a list of the atoms that occur most frequently
in the S-expression $x$.  Thus,
$$\lpile{|most|\,\quote{((A . B) . (C . A))}=\quote{(A)},\cr
|most|\,\quote{(B . ((C . NIL) . (B . NIL)))}=\quote{(B NIL)}.\cr}$$